package com.cat.greedyAlgorithm;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/optimal-partition-of-string/description/
 * @create 2025/10/9 15:24
 * @since JDK17
 */

public class Solution64 {
    public int partitionString(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length, ans = 0, h = 0;
        for (int i = 0; i < n; i++) {
            if (((h >> arr[i] - 'a') & 1) != 0) {    // 重复了
                h = 0;
                ans++;
            }
            h |= 1 << arr[i] - 'a';
        }

        return ans;
    }
}
